package com.review.backpack_01;

public class BP04 {
    /*
    混合背包
    p=−1  表示第 i 种物品只能用1次；
    p=0 表示第 i 种物品可以用无限次；
    p>0 表示第 i 种物品可以使用 p 次；
     */
    public int knapsackProblem(int[] w, int[] v, int[] p, int cap) {
        int[] dp = new int[cap + 1];
        for (int i = 0; i < w.length; i++) {
            if (p[i] == 0) {
                for (int j = w[i]; j <= cap; j++) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            } else {
                for (int j = 1; j <= p[i]; p[i] -= j, j *= 2) {
                    for (int k = cap; k >= 0 && k >= j * w[i]; k--) {
                        dp[k] = Math.max(dp[k], dp[k - j * w[i]] + j * v[i]);
                    }
                }
                if (p[i] > 0) {
                    for (int j = cap; j >= p[i] * w[i]; j--) {
                        dp[j] = Math.max(dp[j], dp[j - p[i] * w[i]] + p[i] * v[i]);
                    }
                }
            }
        }
        return dp[cap];
    }

    public static void main(String[] args) {
        System.out.println(new BP04().knapsackProblem(new int[]{2, 3, 4, 5, 6, 7, 8}, new int[]{3, 4, 5, 6, 7, 8, 9}, new int[]{1, 1, 0, 0, 1, 3, 4}, 27));
        System.out.println(new BP04().knapsackProblem(new int[]{1, 2, 3, 4}, new int[]{2, 4, 4, 5}, new int[]{-1, 1, 0, 2}, 5));
    }

}
